Pairing based cryptography

• Defination of Pairing
• An application: BLS signature scheme

Defination of Pairing

Given cyclic groups ${\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_{\mathbb{T}}$ all same prime order $q$, a $pairing$ is a nondegenerate bilinera map $$e:{\mathbb{G}}_1\times {\mathbb{G}}_2\Rightarrow {\mathbb{G}}_{\mathbb{T}}$$,$G_1\text{ and }{G}_2$ are the generators of ${\mathbb{G}}_1\text{ and }{\mathbb{G}}_2$,respectively.

• Bilinearity: $e(X_1+X_2,Y)=e(X_1,Y)\ast e(X_2,Y)$ and $e(X,Y_1+Y_2)=e(X,Y_1)\ast e(X,Y_2)$
• Non-degeneracy: $G_T:=e(G_1,G_2)\in {\mathbb{G}}_{\mathbb{T}}$ is a generator.
• Computability: There exists an efficient algorithm to compute $e$.

An application: BLS signature scheme

• Keygen: $p,{\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_{\mathbb{T}},G_1,G_2,e$
  • private key: x, and Public key $P=[x]G_1$
• Sign(x,m): $\sigma :=[x]H(m)\in {\mathbb{G}}_2$,$H(m)\in {\mathbb{G}}_2$, where $H$ is a cryptographic hash that maps the message space to ${\mathbb{G}}_2$.
• Verify($P,m,\sigma$): check $e(P,H(m))\stackrel{?}{=}e(G_1,\sigma )$

BLS signature scheme can be extended to allow signature aggregation.